Tree Traversal

    Traverse is one of the basic operations we apply to each data structure. In traverse, we visit every element or node of the data structure, traverse also help in searching operation when we have linear searching. Here we have provided a brief description and a python implementation of traverser operation on a binary tree .

    Tree Traversal

    In Tree Traversal we use recursion statement, to visit each node at least one time. Though we can use the iterative or loop to traverse through each node of the tree, recursion provides a more logical and effective approach. When we perform the traverse operation on the tree, we require a node to start the traverse, there we use the root node of the tree because with root node we can reach any node of the tree. Another reason of starting traverse from a root node, in the tree we do not have a random excess to any node so to traverse or visit any particular node or data we have to start from the root node.

    Types of Tree Traversal

    In the tree, there are three types of traversal algorithms we can use while performing the traversal operations.

    • In-Order Traversal
    • Post-Order Traversal
    • Pre-Order Traversal

    In-Order Traversal

    In In-Order Traversal we visit the left subtree first, then the root and at last the right subtree. Here each node with its child is a subtree. The in-order traverse can be applied on a binary tree where each node can have maximum 2 child node. Algorithm:

    • Use recursion to visit the left node until we found the leaf node.
    • Print the left node value.
    • Now print the root value.
    • Last recursively traverse the right node.

    Example: 

                                  a
                            /   \
                           /     \
                          b       c
                         /  \    /  \
                        d   e   f    g

    Here a is the root node and d, e f, and g are the leaf nodes. If we divide the complete tree into sub tree the sub trees will be [a, b, c], [b, d, e], and [c,f,g]. When we apply the in-order traversal on the above binary tree the order of traversal would be. In-Order = [ d --> b -->  e -->  a  --> f  --> g  --> c ] Code for In-Order Traversal: 

    def in_order(parent_node):
    if parent_node:
        in_order(parent_node.get_left_node())
        print(parent_node.data)
        in_order(parent_node.get_right_node()) 

    Pre-Order Traversal

    In Pre-Order traversal we print the root data or visit the root node first, then the left subtree and at last the right subtree. Here we also use the recursion statement to visit each node.

    Example: 

                                  a
                            /    \
                           /      \
                          b        c
                        /   \    /   \
                       d     e  f     g

    Here a is the root node and d, e f, and g are the leaf nodes. If we divide the complete tree into sub tree the sub trees will be [a, b, c], [b, d, e], and [c,f,g]. When we apply the pre-order traversal on the above binary tree the order of traversal would be. Pre-Order = [ a --> b --> d -->  e --> c  --> f  --> g ] Code for Pre-Order Traversal: 

    def pre_order(parent_node):
    if parent_node:
        print(parent_node.data)
        pre_order(parent_node.get_left_node())
        pre_order(parent_node.get_right_node())

    Post-Order Traversal

    In Post-Order Traversal, we first visit the left node, then the right node and at last, we get the root node. Here we call it to post because the parent node would be the last visited node we have. By visiting mean which value, we print or display in our program, if we logically see the algorithm, we start to visit from the root node, but we print the value of left node first. In the result, you will see the sequence of output and determine the traverse type.

    Example: 

                                   a
                             /   \
                            /     \
                           b       c
                          /  \    /  \
                         d    e  f    g

    Here a is the root node and d, e f, and g are the leaf nodes. If we divide the complete tree into sub tree the sub trees will be [a, b, c], [b, d, e], and [c,f,g]. When we apply the post-order traversal on the above binary tree the order of traversal would be. Post-Order = [ d --> e -->  b -->  f --> g  --> c  --> a ] Code for Post-Order Traversal: 

    def post_order(parent_node):
    if parent_node:
        post_order(parent_node.get_left_node())
        post_order(parent_node.get_right_node())
        print(parent_node.data)

    All the code we have provided for the different traversal methods, all look similar the only difference is the positioning of the print statement, that all matter the print statement determine the traversal method.

    All three Traversal Implementation on A binary Tree: 

    class Binary_Tree():
	def __init__(self,rootobj):
		self.data = rootobj
		self.left = None
		self.right=None
	def insert_left(self,data):
		if self.left==None:
			self.left = Binary_Tree(data)
		else:
			temp= Binary_Tree(data)
			temp.left = self.left
			self.left =temp
	def insert_right(self,data):
		if self.right==None:
			self.right = Binary_Tree(data)
		else:
			temp= Binary_Tree(data)
			temp.right =self.right
			self.left=temp
	def get_right_node(self):
		return self.right
	def get_left_node(self):
		return self.left
def post_order(parent_node):
    if parent_node:
        post_order(parent_node.get_left_node())
        post_order(parent_node.get_right_node())
        print(parent_node.data)
def pre_order(parent_node):
    if parent_node:
        print(parent_node.data)
        pre_order(parent_node.get_left_node())
        pre_order(parent_node.get_right_node())
def in_order(parent_node):
    if parent_node:
        in_order(parent_node.get_left_node())
        print(parent_node.data)
        in_order(parent_node.get_right_node())

    People are also reading:

    Previous Tutorial Next Tutorial